import java.util.HashMap;
import java.util.Map;


public class RecursionExample {
	public static void main(String[] args){
		System.out.println(factorial(5));
		System.out.println(fibonacci(45));
		
		RecursiveList<String> e  = new Empty<String>();
		RecursiveList<String> lst = new Cons<String>("hello", new Cons<String>("world", e));
		System.out.println(lst);
		System.out.println(lst.len());
				
				
	}
	
	public static int factorial(int n){
		if(n == 0){
			return 1;
		}
		else {
			return n*factorial(n-1);
		}
	}
	//f(0) = 1
	//f(1) = 1
	//f(n) = f(n-1) + f(n-2)
	public static Map<Integer, Integer> fiboValues = new HashMap<Integer, Integer>();
	
	
	public static int fibonacci(int n){
		if(n  == 0 || n == 1){
			return 1;
		}
		else if(fiboValues.containsKey(n)){
			return fiboValues.get(n);
		}
		else{
			int res =  fibonacci(n-1) + fibonacci(n-2);
			fiboValues.put(n, res);
			return res;
		}
	}
	
	public static int warlowe(int n){
		if(n == 0 || n == 1 || n == 2){
			return 1;
		}
		else{
			return warlowe(n-1)  +warlowe(n-2) + warlowe(n-3);
		}
	}
	
	//returns 2^n
	public static int mystery(int n){
		if(n==0)
			return 1;
		return 2*mystery(n-1);
	}
	
	/**
	 * Doubles all strings in the input list
	 * @param input
	 * @return
	 */
	public static  RecursiveList<String> mapDouble(RecursiveList<String> input){
		if(input.empty()){
			return new Empty<String>();
		}
		else{
			return new Cons<String>(input.head() + input.head(), mapDouble(input.tail()));
		}
	}
}
